package com.carl.leetcode.pointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by carlXie on 2016/3/13.
 */
public class FourSum {
    public static void main(String[] args) {
        int[] nums = {-3,-2,-1,0,0,1,2,3};
        int target = 0;

        List<List<Integer>> list = fourSum(nums, target);
        for(List<Integer> subList: list) {
            for(Integer val: subList)
                System.out.print(val + " ");
            System.out.println();
        }
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();

        int lastThreeTarget = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 3; i++) {
            int threeTarget = target - nums[i];
            if(threeTarget == lastThreeTarget)
                continue;
            lastThreeTarget = threeTarget;

            int lastTwoTarget = Integer.MAX_VALUE;
            for (int j = i + 1; j < nums.length - 2; j++) {
                int twoTarget = threeTarget - nums[j];
                if(twoTarget == lastTwoTarget)
                    continue;
                lastTwoTarget = twoTarget;
                int front = j + 1;
                int rear = nums.length - 1;

                while(front < rear) {
                    int sum = nums[front] + nums[rear];

                    if(sum < twoTarget) {
                        ++ front;
                    } else if(sum > twoTarget) {
                        -- rear;
                    } else {
                        List<Integer> subList = Arrays.asList(nums[i], nums[j], nums[front], nums[rear]);
                        resultList.add(subList);

                        while(front < rear && nums[front] == subList.get(2))
                            ++ front;
                        while(front < rear && nums[rear] == subList.get(3))
                            -- rear;
                    }
                }
            }

        }

        return resultList;
    }

}
